home *** CD-ROM | disk | FTP | other *** search
/ ADA Programming Guide / ADA Programming Guide.iso / ada_pcdp / adas / adas.doc next >
Text File  |  1996-01-30  |  9KB  |  204 lines
  1.             AdaS Concurrency Simulator
  2.                     for
  3.  
  4.    Principles of Concurrent and Distributed Programming
  5.                  M. Ben-Ari
  6.          Prentice-Hall International
  7.                    1989
  8.  
  9. 1. Introduction
  10.  
  11. The AdaS program simulates concurrent execution of several processes
  12. written in Ada syntax. There are two principle reasons for using AdaS,
  13. even if a true Ada compiler is available:
  14.  
  15.   a. Some Ada compilers may not implement time slicing. Therefore,
  16. they cannot execute the common memory algorithms.
  17.  
  18.   b. Even if time-slicing is implemented, the user may not be able to
  19. control the scheduler in sufficient detail to demonstrate the pathological
  20. behavior described in the book.
  21.  
  22. For example, AdaS can demonstrate livelock in the fourth example of
  23. Chapter 3 which is caused by perfect interleaving of the instructions
  24. of two processes.
  25.  
  26. AdaS is NOT an Ada interpreter. It accepts only very small fragment of
  27. the language, it does not reject all incorrect programs and there are
  28. some deviations from Ada semantics. It is best used as a laboratory
  29. instrument where an example program is initially written using a true
  30. compiler and then transfered to AdaS for microscopic examination.
  31.  
  32. 2. Implementation
  33.  
  34. AdaS is a descendent of the Pascal-S interpreter written by N. Wirth of
  35. ETH (Zurich, Switzerland) in 1976. Pascal-S is described in [1].
  36. The interpreter was modified to support concurrency by the author [2].
  37. AdaS is a modification of this concurrent interpreter to accept Ada
  38. syntax and the Ada rendezvous. Finally, the user interface has been
  39. improved to support microscopic control of the concurrency scheduler.
  40.  
  41. The program was written using Turbo Pascal (version 5.0) from Borland
  42. International on PC-compatible personal computers. The deviations
  43. from standard Pascal are relatively minor, except for the use of Units
  44. to break up the program into modules. Since units are common in other
  45. dialects of Pascal, it should be possible to port the program.
  46.  
  47. 3. Specification
  48.  
  49. The following fragment of the Ada language is supported:
  50.  
  51. 3.1 Constants, variables and expressions of type integer, character
  52. and boolean. Arithmetical and logical operators on integers and booleans.
  53. Initial values for static variables. Assignment statements. One
  54. dimensional arrays of the predefined types. No array assignments.
  55.  
  56. 3.2 Control statements: loop (infinite or with exit), for, while,
  57. if, null.
  58.  
  59. 3.3 Procedures (no functions) with parameters. "in" mode uses copy
  60. semantics and "out" or "in out" use reference semantics like Pascal.
  61. No default parameters.
  62.  
  63. 3.4 Text_IO procedures: get, put, skip_line, new_line, put_line.
  64.  
  65. 3.5 Tasks objects (up to 3) declared in the main procedure. Entry calls
  66. and accept statements which may have up to two parameters of mode
  67. "in" or "out" and predefined type. The task specification is ignored
  68. and the first accept statement is the defining occurence of the entry.
  69. Hence the entry calls can only be used in tasks declared after the
  70. accepting task.
  71.  
  72. 3.6 One task may have a two branch select statement with guards and a
  73. terminate alternative. This is designed to allow a bounded buffer
  74. to be programmed.
  75.  
  76. 3.7 Semaphores (as if they were declared in a package).
  77.  
  78. 3.8 Context clauses and pragmas are ignored. This facilitates transfering
  79. a program from a true compiler to AdaS.
  80.  
  81. 4. Usage
  82.  
  83. Upon executing AdaS, it prompts for the name of a source file.
  84. A non-alphabetic first character will terminate AdaS.
  85. The extension ".ADA" is added to the name entered. The next prompt
  86. asked if a listing is requested. If so, it will be created on a
  87. file with the same name and with the extension ".LIS".
  88. The listing file will contain the source statements as well
  89. as the "machine code", i.e. the byte codes generated for use
  90. by the interpreter.
  91.  
  92. If compilation is unsuccessful, the incorrect line will be
  93. displayed. As in Turbo Pascal, no attempt is made to continue
  94. compilation after an error. Press return to terminate the AdaS.
  95.  
  96. If compilation is successful, AdaS prompts to ask if the program
  97. should be interpreted. If so, the next prompt asks for process
  98. priorities. A zero answer gives all processes the same priority.
  99. Otherwise, enter three priorities from the range 1 to 3 for the
  100. three processes in the program.
  101.  
  102. The screen is now divided into three windows. The upper half
  103. of the screen is the program window which displays the results
  104. of print statements from within the program. The lower right
  105. window is the watch window which displays the values of global
  106. variables as they change (note: the initial value is not displayed).
  107.  
  108. The lower left window prints the status of the processes and
  109. accepts commands from the user. For each process the following
  110. information is displayed: its index, suspension status (0 = active,
  111. 999 = inactive, other positive integer = entry or semaphore
  112. upon which it is suspended), current program counter and the
  113. instruction at that location. For each entry, one of two lines of
  114. information is displayed. The process index and pc of a task
  115. suspended at an accept statement for the entry, or the callers
  116. (process index and time-stamp) that are engaged in a rendezvous
  117. or waiting in the entry queue.
  118.  
  119. The following commands are accepted:
  120.   * - execute one instruction of the current process
  121.   + - execute one instruction of the next process
  122.   - - execute until termination
  123.   / - terminate program
  124.  (space) - the program prompts for a (positive) number of steps to
  125.            execute before breaking again
  126.  
  127. At any time, pressing a key such as space will break the execution
  128. of the program and prompt for a new command.
  129.  
  130. 5. Examples
  131.  
  132. The directory contains several Ada programs that have been
  133. executed using AdaS:
  134.  
  135.   incr   - simultaneous increment of a global integer
  136.   first  - first attempt at mutual exclusion
  137.   second - second attempt at mutual exclusion
  138.   third  - third attempt at mutual exclusion
  139.   fourth - fourth attempt at mutual exclusion
  140.   dekker - Dekker's algorithm
  141.   peter  - Peterson's algorithm
  142.   mesem  - mutual exclusion using semaphores
  143.   pca    - producer-consumer using bounded buffer in Ada
  144.  
  145. If the "+" key is used to acheive perfect interleaving, then
  146. the third attempt will deadlock and the fourth attempt will livelock.
  147. Try changing priorities to vary the behavior of the producer-consumer.
  148.  
  149. In addition, a program "ren.ada" has two tasks calling the same
  150. entry in a third task. Giving the calling tasks higher priority than
  151. the accepting task can be used to demonstrate the FIFO entry queues.
  152. Note that this program will deadlock; use '/' to terminate execution.
  153.  
  154. 6. Documentation
  155.  
  156. The AdaS program consists of 7 files:
  157.  
  158.   adas     - main program
  159.   global   - global constants, types and variables
  160.   compile  - main program of the compiler
  161.   util     - utility programs used by the compiler
  162.   expr     - compilation of expressions
  163.   state    - compilation of statements
  164.   interp   - the concurrent interpreter
  165.  
  166. The compiler is a simple recursive descent compiler like the one
  167. described in [3]. It has been simplified further by removing
  168. recovery and terminating upon discovery of an error.
  169. The interpreter consists of a loop that executes the byte
  170. codes that were emitted by the compiler. The code is for
  171. a stack based machine with no registers and is quite straightforward
  172. except for procedure calls and tasking. These are explained in [2].
  173. The four units of the compiler are relatively independent of the
  174. interpreter so that it should be possible to modify the interpreter
  175. without a detailed understanding of the compiler.
  176.  
  177. Simulation of entry call and accept is done by keeping a table of
  178. entries which records the program counter of a waiting accept
  179. statement and the process index of a waiting call. Calls are
  180. time-stamped to maintain the FIFO queue. Passing parameters
  181. from one task to another is difficult and is done by having
  182. the calling process store the parameters (values for "in" mode
  183. and addresses for "out" mode) in its process table where they can
  184. be picked up by the accepting task.
  185.  
  186. Select is simulated by checking each guard and each entry
  187. queue sequentially. Random selection of an alternative is done
  188. by skipping the first alternative conditionally upon the value
  189. of a random number. An extra loop around the select processing
  190. ensures that the first alternative is still taken if the
  191. second is closed. If the task with the select notes that it is
  192. the only task left it terminates, thus simulating the terminate alternative.
  193.  
  194. The Ada tasking support of the AdaS program is heavily commented to 
  195. assist readers who wish to modify the program.
  196.  
  197. 7. References
  198.  
  199. [1] D.W. Barron. Pascal-the Language and its Implementation.
  200.     John Wiley. 1981.
  201. [2] M. Ben-Ari. Principles of Concurrent Programming.
  202.     Prentice-Hall International. 1982.
  203. [3] J. Welsh and M. McKeag. Structured System Programming.
  204.     Prentice-Hall International. 1980.